﻿//
// typespec.cs: Type specification
//
// Authors: Marek Safar (marek.safar@gmail.com)
//
// Dual licensed under the terms of the MIT X11 or GNU GPL
//
// Copyright 2010 Novell, Inc
// Copyright 2011 Xamarin, Inc (http://www.xamarin.com)
//

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

#if STATIC
using MetaType = IKVM.Reflection.Type;
using IKVM.Reflection;
#else
using MetaType = System.Type;
using System.Reflection;
#endif

namespace Teal.Compiler {
    //
    // Inflated or non-inflated representation of any type. 
    //
    public partial class TypeReference : NamespaceReference {
        
        Dictionary<TypeReference[], GenericTypeReference> inflated_instances;

        public static readonly TypeReference[] EmptyTypes = new TypeReference[0];

#if !STATIC
        // Reflection Emit hacking
        static readonly Type TypeBuilder;
        static readonly Type GenericTypeBuilder;

        static TypeReference() {
            var assembly = typeof(object).Assembly;
            TypeBuilder = assembly.GetType("System.Reflection.Emit.TypeBuilder");
            GenericTypeBuilder = assembly.GetType("System.Reflection.MonoGenericClass");
            if (GenericTypeBuilder == null)
                GenericTypeBuilder = assembly.GetType("System.Reflection.Emit.TypeBuilderInstantiation");
        }
#endif

        public TypeReference(MemberKind kind, TypeReference declaringType, ITypeDefinition definition, MetaType info, Modifiers modifiers)  {
            this.containerType = declaringType;
            this.metaInfo = info;

            if (definition != null && definition.TypeParametersCount > 0)
                resolveFlags |= ResolveFlags.IsGeneric;
        }

        #region Properties

        public virtual BuiltinTypeSpec.Type BuiltinType {
            get {
                return BuiltinTypeSpec.Type.None;
            }
        }

        public bool HasDynamicElement {
            get {
                return (resolveFlags & ResolveFlags.HasDynamicElement) != 0;
            }
        }

        public bool IsArray {
            get {
                return Kind == MemberKind.ArrayType;
            }
        }

        public bool IsAttribute {
            get {
                if (!IsClass)
                    return false;

                var type = this;
                do {
                    if (type.BuiltinType == BuiltinTypeSpec.Type.Attribute)
                        return true;

                    if (type.IsGeneric)
                        return false;

                    type = type._baseClass;
                } while (type != null);

                return false;
            }
        }

        public bool IsInterface {
            get {
                return Kind == MemberKind.Interface;
            }
        }

        public bool IsClass {
            get {
                return Kind == MemberKind.Class;
            }
        }

        public bool IsConstantCompatible {
            get {
                if ((Kind & (MemberKind.Enum | MemberKind.Class | MemberKind.Interface | MemberKind.Delegate | MemberKind.ArrayType)) != 0)
                    return true;

                switch (BuiltinType) {
                    case BuiltinTypeSpec.Type.Int:
                    case BuiltinTypeSpec.Type.UInt:
                    case BuiltinTypeSpec.Type.Long:
                    case BuiltinTypeSpec.Type.ULong:
                    case BuiltinTypeSpec.Type.Float:
                    case BuiltinTypeSpec.Type.Double:
                    case BuiltinTypeSpec.Type.Char:
                    case BuiltinTypeSpec.Type.Short:
                    case BuiltinTypeSpec.Type.Decimal:
                    case BuiltinTypeSpec.Type.Bool:
                    case BuiltinTypeSpec.Type.SByte:
                    case BuiltinTypeSpec.Type.Byte:
                    case BuiltinTypeSpec.Type.UShort:
                    case BuiltinTypeSpec.Type.Dynamic:
                        return true;
                }

                return false;
            }
        }

        public bool IsDelegate {
            get {
                return Kind == MemberKind.Delegate;
            }
        }

        //
        // Returns true for instances of Expression<T>
        //
        public virtual bool IsExpressionTreeType {
            get {
                return false;
            }
            set {
                resolveFlags = value ? resolveFlags | ResolveFlags.InflatedExpressionType : resolveFlags & ~ResolveFlags.InflatedExpressionType;
            }
        }

        public bool IsEnum {
            get {
                return Kind == MemberKind.Enum;
            }
        }

        //
        // Returns true for instances of IList<T>, IEnumerable<T>, ICollection<T>
        //
        public virtual bool IsArrayGenericInterface {
            get {
                return false;
            }
            set {
                resolveFlags = value ? resolveFlags | ResolveFlags.GenericIterateInterface : resolveFlags & ~ResolveFlags.GenericIterateInterface;
            }
        }

        //
        // Returns true for instances of System.Threading.Tasks.Task<T>
        //
        public virtual bool IsGenericTask {
            get {
                return false;
            }
            set {
                resolveFlags = value ? resolveFlags | ResolveFlags.GenericTask : resolveFlags & ~ResolveFlags.GenericTask;
            }
        }

        // TODO: Should probably do
        // IsGenericType -- recursive
        // HasTypeParameter -- non-recursive
        public bool IsGenericOrParentIsGeneric {
            get {
                var ts = this;
                do {
                    if (ts.IsGeneric)
                        return true;
                    ts = ts.containerType;
                } while (ts != null);

                return false;
            }
        }

        public bool IsGenericParameter {
            get {
                return Kind == MemberKind.TypeParameter;
            }
        }

        //
        // Returns true for instances of Nullable<T>
        //
        public virtual bool IsNullableType {
            get {
                return false;
            }
            set {
                resolveFlags = value ? resolveFlags | ResolveFlags.InflatedNullableType : resolveFlags & ~ResolveFlags.InflatedNullableType;
            }
        }

        public bool IsNested {
            get { return containerType != null && Kind != MemberKind.TypeParameter; }
        }

        public bool IsPointer {
            get {
                return Kind == MemberKind.PointerType;
            }
        }

        public bool IsSealed {
            get { return (modifiers & Modifiers.final) != 0; }
        }

        public bool IsSpecialRuntimeType {
            get {
                return (resolveFlags & ResolveFlags.SpecialRuntimeType) != 0;
            }
            set {
                resolveFlags = value ? resolveFlags | ResolveFlags.SpecialRuntimeType : resolveFlags & ~ResolveFlags.SpecialRuntimeType;
            }
        }

        public bool IsStruct {
            get {
                return Kind == MemberKind.Struct;
            }
        }

        public bool IsStructOrEnum {
            get {
                return (Kind & (MemberKind.Struct | MemberKind.Enum)) != 0;
            }
        }

        public bool IsTypeBuilder {
            get {
#if STATIC
				return true;
#else
                var meta = GetMetaInfo().GetType();
                return meta == TypeBuilder || meta == GenericTypeBuilder;
#endif
            }
        }

        //
        // Whether a type is unmanaged. This is used by the unsafe code
        //
        public bool IsUnmanaged {
            get {
                if (IsPointer)
                    return ((ElementTypeSpec)this).Element.IsUnmanaged;

                var ds = MemberDefinition2 as TypeDefinition;
                if (ds != null)
                    return ds.IsUnmanagedType();

                if (Kind == MemberKind.Void)
                    return true;

                if (Kind == MemberKind.TypeParameter)
                    return false;

                if (IsNested && containerType.IsGenericOrParentIsGeneric)
                    return false;

                return IsValueType(this);
            }
        }

        // TODO: Wouldn't be better to rely on cast to InflatedTypeSpec and
        // remove the property, YES IT WOULD !!!
        public virtual TypeReference[] TypeArguments {
            get { return TypeReference.EmptyTypes; }
        }

        #endregion

        //
        // Returns all type arguments, usefull for nested types
        //
        public static TypeReference[] GetAllTypeArguments(TypeReference type) {
            IList<TypeReference> targs = TypeReference.EmptyTypes;

            do {
                if (type.genericParameterCount > 0) {
                    if (targs.Count == 0) {
                        targs = type.TypeArguments;
                    } else {
                        var list = targs as List<TypeReference> ?? new List<TypeReference>(targs);
                        list.AddRange(type.TypeArguments);
                        targs = list;
                    }
                }

                type = type.containerType;
            } while (type != null);

            return targs as TypeReference[] ?? ((List<TypeReference>)targs).ToArray();
        }

        public AttributeUsageAttribute GetAttributeUsage(PredefinedAttribute pa) {
            if (Kind != MemberKind.Class)
                throw new InternalErrorException();

            if (!pa.IsDefined)
                return Teal.Compiler.MemberDefinition.MemberAnnotation.DefaultUsageAttribute;

            AttributeUsageAttribute aua = null;
            var type = this;
            while (type != null) {
                aua = type.MemberDefinition2.GetAttributeUsage(pa);
                if (aua != null)
                    break;

                type = type.baseClass;
            }

            return aua;
        }

        //
        // Return metadata information used during emit to describe the type
        //
        public virtual MetaType GetMetaInfo() {
            return metaInfo;
        }

        public virtual TypeReference GetDefinition() {
            return this;
        }

        //
        // Text representation of type used by documentation writer
        //

        public string GetExplicitNameSignatureForDocumentation() {
            StringBuilder sb = new StringBuilder();
            if (IsNested) {
                sb.Append(containerType.GetExplicitNameSignatureForDocumentation());
            } else if (MemberDefinition2.Namespace != null) {
                sb.Append(MemberDefinition2.Namespace.Replace('.', '#'));
            }

            if (sb.Length != 0)
                sb.Append("#");

            sb.Append(name);
            if (genericParameterCount > 0) {
                sb.Append("{");
                for (int i = 0; i < genericParameterCount; ++i) {
                    if (i > 0)
                        sb.Append(",");

                    sb.Append(TypeArguments[i].GetExplicitNameSignatureForDocumentation());
                }
                sb.Append("}");
            }

            return sb.ToString();
        }

        public override string GetSignatureForError() {
            string s;

            if (IsNested) {
                s = containerType.GetSignatureForError();
            } else if (MemberDefinition2 is AnonymousTypeClass) {
                return ((AnonymousTypeClass)MemberDefinition2).GetSignatureForError();
            } else {
                s = MemberDefinition2.Namespace;
            }

            if (!string.IsNullOrEmpty(s))
                s += ".";

            return s + name + GetTypeNameSignature();
        }

        public string GetSignatureForErrorIncludingAssemblyName() {
            return string.Format("{0} [{1}]", GetSignatureForError(), MemberDefinition2.DeclaringAssembly.FullName);
        }

        protected virtual string GetTypeNameSignature() {
            if (!IsGeneric)
                return null;

            return "<" + TypeManager.CSharpName(MemberDefinition2.TypeParameters) + ">";
        }

        public bool ImplementsInterface(TypeReference iface, bool variantly) {
            var ifaces = baseInterfaces;
            if (ifaces != null) {
                for (int i = 0; i < ifaces.Count; ++i) {
                    if (TypeSpecComparer.IsEqual(ifaces[i], iface))
                        return true;

                    if (variantly && TypeSpecComparer.Variant.IsEqual(ifaces[i], iface))
                        return true;
                }
            }

            return false;
        }

        //
        // Is @baseClass base implementation of @type. With enabled @dynamicIsEqual the slower
        // comparison is used to hide differences between `object' and `dynamic' for generic
        // types. Should not be used for comparisons where G<object> != G<dynamic>
        //
        public static bool IsBaseClass(TypeReference type, TypeReference baseClass, bool dynamicIsObject) {
            if (dynamicIsObject && baseClass.IsGeneric) {
                //
                // Returns true for a hierarchies like this when passing baseClass of A<dynamic>
                //
                // class B : A<object> {}
                //
                type = type.baseClass;
                while (type != null) {
                    if (TypeSpecComparer.IsEqual(type, baseClass))
                        return true;

                    type = type.baseClass;
                }

                return false;
            }

            while (type != null) {
                type = type.baseClass;
                if (type == baseClass)
                    return true;
            }

            return false;
        }

        public static bool IsReferenceType(TypeReference t) {
            switch (t.Kind) {
                case MemberKind.TypeParameter:
                    return ((MemberReference.GenericParameter)t).IsReferenceType;
                case MemberKind.Struct:
                case MemberKind.Enum:
                case MemberKind.Void:
                case MemberKind.PointerType:
                    return false;
                case MemberKind.InternalCompilerType:
                    //
                    // Null is considered to be a reference type
                    //			
                    return t == InternalType.NullLiteral || t.BuiltinType == BuiltinTypeSpec.Type.Dynamic;
                default:
                    return true;
            }
        }

        public static bool IsNonNullableValueType(TypeReference t) {
            switch (t.Kind) {
                case MemberKind.TypeParameter:
                    return ((MemberReference.GenericParameter)t).IsValueType;
                case MemberKind.Struct:
                    return !t.IsNullableType;
                case MemberKind.Enum:
                    return true;
                default:
                    return false;
            }
        }

        public static bool IsValueType(TypeReference t) {
            switch (t.Kind) {
                case MemberKind.TypeParameter:
                    return ((MemberReference.GenericParameter)t).IsValueType;
                case MemberKind.Struct:
                case MemberKind.Enum:
                    return true;
                default:
                    return false;
            }
        }

        //
        // Inflates current type using specific type arguments
        //
        public GenericTypeReference MakeGenericType(TypeReference[] targs) {
            if (targs.Length == 0 && !IsNested)
                throw new ArgumentException("Empty type arguments for type " + GetSignatureForError());

            GenericTypeReference instance;

            if (inflated_instances == null) {
                inflated_instances = new Dictionary<TypeReference[], GenericTypeReference>(TypeReferenceArrayComparer.@default);

                if (IsNested) {
                    instance = this as GenericTypeReference;
                    if (instance != null) {
                        //
                        // Nested types could be inflated on already inflated instances
                        // Caching this type ensured we are using same instance for
                        // inside/outside inflation using local type parameters
                        //
                        inflated_instances.Add(TypeArguments, instance);
                    }
                }
            }

            if (!inflated_instances.TryGetValue(targs, out instance)) {
                if (GetDefinition() != this && !IsNested)
                    throw new InternalErrorException("`{0}' must be type definition or nested non-inflated type to MakeGenericType",
                        GetSignatureForError());

                instance = new GenericTypeReference(this, containerType, targs);
                inflated_instances.Add(targs, instance);
            }

            return instance;
        }

        public virtual TypeReference Mutate(TypeParameterMutator mutator) {
            return this;
        }

        public override List<MissingTypeSpecReference> ResolveMissingDependencies(MemberReference caller) {
            List<MissingTypeSpecReference> missing = null;

            if (Kind == MemberKind.MissingType) {
                missing = new List<MissingTypeSpecReference>();
                missing.Add(new MissingTypeSpecReference(this, caller));
                return missing;
            }

            foreach (var targ in TypeArguments) {
                if (targ.Kind == MemberKind.MissingType) {
                    if (missing == null)
                        missing = new List<MissingTypeSpecReference>();

                    missing.Add(new MissingTypeSpecReference(targ, caller));
                }
            }

            if (baseInterfaces != null) {
                foreach (var iface in baseInterfaces) {
                    if (iface.Kind == MemberKind.MissingType) {
                        if (missing == null)
                            missing = new List<MissingTypeSpecReference>();

                        missing.Add(new MissingTypeSpecReference(iface, caller));
                    }
                }
            }

            if (MemberDefinition2.TypeParametersCount > 0) {
                foreach (var tp in MemberDefinition2.TypeParameters) {
                    var tp_missing = tp.GetMissingDependencies(this);
                    if (tp_missing != null) {
                        if (missing == null)
                            missing = new List<MissingTypeSpecReference>();

                        missing.AddRange(tp_missing);
                    }
                }
            }

            if (missing != null || baseClass == null)
                return missing;

            return baseClass.ResolveMissingDependencies(this);
        }

        public void SetMetaInfo(MetaType info) {
            if (this.metaInfo != null)
                throw new InternalErrorException("MetaInfo reset");

            this.metaInfo = info;
        }

        public void SetExtensionMethodContainer() {
            modifiers |= Modifiers.METHOD_EXTENSION;
        }

        public void UpdateInflatedInstancesBaseType() {
            //
            // When nested class has a partial part the situation where parent type
            // is inflated before its base type is defined can occur. In such case
            // all inflated (should be only 1) instansted need to be updated
            //
            // partial class A<T> {
            //   partial class B : A<int> { }
            // }
            //
            // partial class A<T> : X {}
            //
            if (inflated_instances == null)
                return;

            foreach (var inflated in inflated_instances) {
                //
                // Don't need to inflate possible generic type because for now the method
                // is always used from within the nested type
                //
                inflated.Value.baseClass = _baseClass;
            }
        }
    }

    //
    // Special version used for types which must exist in corlib or
    // the compiler cannot work
    //
    public sealed class BuiltinTypeSpec : TypeReference {
        public enum Type {
            None = 0,

            // Ordered carefully for fast compares
            FirstPrimitive = 1,
            Bool = 1,
            Byte = 2,
            SByte = 3,
            Char = 4,
            Short = 5,
            UShort = 6,
            Int = 7,
            UInt = 8,
            Long = 9,
            ULong = 10,
            Float = 11,
            Double = 12,
            LastPrimitive = 12,
            Decimal = 13,

            IntPtr = 14,
            UIntPtr = 15,

            Object = 16,
            Dynamic = 17,
            String = 18,
            Type = 19,

            ValueType = 20,
            Enum = 21,
            Delegate = 22,
            MulticastDelegate = 23,
            Array = 24,

            IEnumerator,
            IEnumerable,
            IDisposable,
            Exception,
            Attribute,
            Other,
        }

        readonly Type type;
        readonly string ns;

        public BuiltinTypeSpec(MemberKind kind, string ns, string name, Type builtinKind)
            : base(kind, null, null, null, Modifiers.@public) {
            this.type = builtinKind;
            this.ns = ns;
            this.name = name;
        }

        public BuiltinTypeSpec(string name, Type builtinKind)
            : this(MemberKind.InternalCompilerType, "", name, builtinKind) {
            // Make all internal types CLS-compliant, non-obsolete, compact
            resolveFlags = (resolveFlags & ~(ResolveFlags.Obsolete_Undetected | ResolveFlags.MissingDependency_Undetected));
        }

        #region Properties

        public override BuiltinTypeSpec.Type BuiltinType {
            get {
                return type;
            }
        }

        public string FullName {
            get {
                return ns + '.' + name;
            }
        }

        public string Namespace {
            get {
                return ns;
            }
        }

        #endregion

        public static bool IsPrimitiveType(TypeReference type) {
            return type.BuiltinType >= Type.FirstPrimitive && type.BuiltinType <= Type.LastPrimitive;
        }

        public static bool IsPrimitiveTypeOrDecimal(TypeReference type) {
            return type.BuiltinType >= Type.FirstPrimitive && type.BuiltinType <= Type.Decimal;
        }

        public override string GetSignatureForError() {
            switch (name) {
                case "Int32": return "int";
                case "Int64": return "long";
                case "String": return "string";
                case "Boolean": return "bool";
                case "Void": return "void";
                case "Object": return "object";
                case "UInt32": return "uint";
                case "Int16": return "short";
                case "UInt16": return "ushort";
                case "UInt64": return "ulong";
                case "Single": return "float";
                case "Double": return "double";
                case "Decimal": return "decimal";
                case "Char": return "char";
                case "Byte": return "byte";
                case "SByte": return "sbyte";
            }

            if (ns.Length == 0)
                return name;

            return FullName;
        }

        //
        // Returns the size of type if known, otherwise, 0
        //
        public static int GetSize(TypeReference type) {
            switch (type.BuiltinType) {
                case Type.Int:
                case Type.UInt:
                case Type.Float:
                    return 4;
                case Type.Long:
                case Type.ULong:
                case Type.Double:
                    return 8;
                case Type.Byte:
                case Type.SByte:
                case Type.Bool:
                    return 1;
                case Type.Short:
                case Type.Char:
                case Type.UShort:
                    return 2;
                case Type.Decimal:
                    return 16;
                default:
                    return 0;
            }
        }

        public void SetDefinition(ITypeDefinition td, MetaType type, Modifiers mod) {
            this.definition2 = td;
            this.metaInfo = type;
            this.modifiers |= (mod & ~Modifiers.ACCESSIBILITY);
        }

        public void SetDefinition(TypeReference ts) {
            this.definition2 = ts.MemberDefinition2;
            this.metaInfo = ts.GetMetaInfo();
            this.baseClass = ts.baseClass;
            this.baseInterfaces = ts.baseInterfaces;
            this.modifiers = ts.modifiers;
        }
    }

    //
    // Various type comparers used by compiler
    //
    static class TypeSpecComparer {
       
        //
        // When comparing type signature of overrides or overloads
        // this version tolerates different MVARs at same position
        //
        public static class Override {
            public static bool IsEqual(TypeReference a, TypeReference b) {
                return ResolveHelper.isOverriding(a, b);
            }

            public static bool IsEqual(TypeReference[] a, TypeReference[] b) {
                if (a == b)
                    return true;

                if (a.Length != b.Length)
                    return false;

                for (int i = 0; i < a.Length; ++i) {
                    if (!IsEqual(a[i], b[i]))
                        return false;
                }

                return true;
            }


            //
            // Compares unordered arrays
            //
            public static bool IsSame(TypeReference[] a, TypeReference[] b) {
                if (a == b)
                    return true;

                if (a == null || b == null || a.Length != b.Length)
                    return false;

                for (int ai = 0; ai < a.Length; ++ai) {
                    bool found = false;
                    for (int bi = 0; bi < b.Length; ++bi) {
                        if (IsEqual(a[ai], b[bi])) {
                            found = true;
                            break;
                        }
                    }

                    if (!found)
                        return false;
                }

                return true;
            }

            public static bool IsEqual(AParametersCollection a, AParametersCollection b) {
                if (a == b)
                    return true;

                if (a.Count != b.Count)
                    return false;

                for (int i = 0; i < a.Count; ++i) {
                    if (!IsEqual(a.Types[i], b.Types[i]))
                        return false;

                    if ((a.FixedParameters[i].ModFlags & Parameter2.Modifier.RefOutMask) != (b.FixedParameters[i].ModFlags & Parameter2.Modifier.RefOutMask))
                        return false;
                }

                return true;
            }
        }

        //
        // Type variance equality comparison
        //
        public static class Variant {
            public static bool IsEqual(TypeReference type1, TypeReference type2) {
                if (!type1.IsGeneric || !type2.IsGeneric)
                    return false;

                var target_type_def = type2.MemberDefinition2;
                if (type1.MemberDefinition2 != target_type_def)
                    return false;

                var t1_targs = type1.TypeArguments;
                var t2_targs = type2.TypeArguments;
                var targs_definition = target_type_def.TypeParameters;

                if (!type1.IsInterface && !type1.IsDelegate) {
                    return false;
                }

                for (int i = 0; i < targs_definition.Length; ++i) {
                    if (TypeSpecComparer.IsEqual(t1_targs[i], t2_targs[i]))
                        continue;

                    Variance v = targs_definition[i].Variance;
                    if (v == Variance.None) {
                        return false;
                    }

                    if (v == Variance.Covariant) {
                        if (!Convert.ImplicitReferenceConversionExists(t1_targs[i], t2_targs[i]))
                            return false;
                    } else if (!Convert.ImplicitReferenceConversionExists(t2_targs[i], t1_targs[i])) {
                        return false;
                    }
                }

                return true;
            }
        }

        //
        // Checks whether two generic instances may become equal for some
        // particular instantiation (26.3.1).
        //
        public static class Unify {
            //
            // Either @a or @b must be generic type
            //
            public static bool IsEqual(TypeReference a, TypeReference b) {
                if (a.MemberDefinition2 != b.MemberDefinition2) {
                    var base_ifaces = a.baseInterfaces;
                    if (base_ifaces != null) {
                        foreach (var base_iface in base_ifaces) {
                            if (base_iface.genericParameterCount > 0 && IsEqual(base_iface, b))
                                return true;
                        }
                    }

                    return false;
                }

                var ta = a.TypeArguments;
                var tb = b.TypeArguments;
                for (int i = 0; i < ta.Length; i++) {
                    if (!MayBecomeEqualGenericTypes(ta[i], tb[i]))
                        return false;
                }

                if (a.IsNested && b.IsNested)
                    return IsEqual(a.containerType, b.containerType);

                return true;
            }

            static bool ContainsTypeParameter(TypeReference tparam, TypeReference type) {
                TypeReference[] targs = type.TypeArguments;
                for (int i = 0; i < targs.Length; i++) {
                    if (tparam == targs[i])
                        return true;

                    if (ContainsTypeParameter(tparam, targs[i]))
                        return true;
                }

                return false;
            }

            /// <summary>
            ///   Check whether `a' and `b' may become equal generic types.
            ///   The algorithm to do that is a little bit complicated.
            /// </summary>
            static bool MayBecomeEqualGenericTypes(TypeReference a, TypeReference b) {
                if (a.IsGenericParameter) {
                    //
                    // If a is an array of a's type, they may never
                    // become equal.
                    //
                    if (b.IsArray)
                        return false;

                    //
                    // If b is a generic parameter or an actual type,
                    // they may become equal:
                    //
                    //    class X<T,U> : I<T>, I<U>
                    //    class X<T> : I<T>, I<float>
                    // 
                    if (b.IsGenericParameter)
                        return a != b && a.containerType == b.containerType;

                    //
                    // We're now comparing a type parameter with a
                    // generic instance.  They may become equal unless
                    // the type parameter appears anywhere in the
                    // generic instance:
                    //
                    //    class X<T,U> : I<T>, I<X<U>>
                    //        -> error because you could instanciate it as
                    //           X<X<int>,int>
                    //
                    //    class X<T> : I<T>, I<X<T>> -> ok
                    //

                    return !ContainsTypeParameter(a, b);
                }

                if (b.IsGenericParameter)
                    return MayBecomeEqualGenericTypes(b, a);

                //
                // At this point, neither a nor b are a type parameter.
                //
                // If one of them is a generic instance, compare them (if the
                // other one is not a generic instance, they can never
                // become equal).
                //
                if (TypeManager.IsGenericType(a) || TypeManager.IsGenericType(b))
                    return IsEqual(a, b);

                //
                // If both of them are arrays.
                //
                var a_ac = a as ArrayContainer;
                if (a_ac != null) {
                    var b_ac = b as ArrayContainer;
                    if (b_ac == null || a_ac.Rank != b_ac.Rank)
                        return false;

                    return MayBecomeEqualGenericTypes(a_ac.Element, b_ac.Element);
                }

                //
                // Ok, two ordinary types.
                //
                return false;
            }
        }

        public static bool Equals(TypeReference[] x, TypeReference[] y) {
            if (x == y)
                return true;

            if (x.Length != y.Length)
                return false;

            for (int i = 0; i < x.Length; ++i)
                if (!IsEqual(x[i], y[i]))
                    return false;

            return true;
        }

        //
        // Identity type conversion
        //
        // Default reference comparison, it has to be used when comparing
        // two possible dynamic/internal types
        //
        public static bool IsEqual(TypeReference a, TypeReference b) {
            if (a == b) {
                // This also rejects dynamic == dynamic
                return a.Kind != MemberKind.InternalCompilerType || a.BuiltinType == BuiltinTypeSpec.Type.Dynamic;
            }

            if (a == null || b == null)
                return false;

            if (a.IsArray) {
                var a_a = (ArrayContainer)a;
                var b_a = b as ArrayContainer;
                if (b_a == null)
                    return false;

                return a_a.Rank == b_a.Rank && IsEqual(a_a.Element, b_a.Element);
            }

            if (!a.IsGeneric || !b.IsGeneric) {
                //
                // object and dynamic are considered equivalent there is an identity conversion
                // between object and dynamic, and between constructed types that are the same
                // when replacing all occurences of dynamic with object.
                //
                if (a.BuiltinType == BuiltinTypeSpec.Type.Dynamic || b.BuiltinType == BuiltinTypeSpec.Type.Dynamic)
                    return b.BuiltinType == BuiltinTypeSpec.Type.Object || a.BuiltinType == BuiltinTypeSpec.Type.Object;

                return false;
            }

            if (a.MemberDefinition2 != b.MemberDefinition2)
                return false;

            do {
                if (!Equals(a.TypeArguments, b.TypeArguments))
                    return false;

                a = a.containerType;
                b = b.containerType;
            } while (a != null);

            return true;
        }
    }

    public interface ITypeDefinition : IMemberDefinition {
        PackageDefinition DeclaringAssembly { get; }
        string Namespace { get; }

        bool IsComImport { get; }
        bool IsTypeForwarder { get; }
        bool IsCyclicTypeForwarder { get; }
        int TypeParametersCount { get; }
        MemberReference.GenericParameter[] TypeParameters { get; }

        TypeReference GetAttributeCoClass();
        string GetAttributeDefaultMember();
        AttributeUsageAttribute GetAttributeUsage(PredefinedAttribute pa);
        bool IsInternalAsPublic(PackageDefinition assembly);
        void LoadMembers(TypeReference declaringType, bool onlyTypes, ref MemberCache cache);
    }

    class InternalType : TypeReference, ITypeDefinition {
        public static readonly InternalType AnonymousMethod = new InternalType("anonymous method");
        public static readonly InternalType Arglist = new InternalType("__arglist");
        public static readonly InternalType MethodGroup = new InternalType("method group");
        public static readonly InternalType NullLiteral = new InternalType("null");
        public static readonly InternalType FakeInternalType = new InternalType("<fake$type>");
        public static readonly InternalType Namespace = new InternalType("<namespace>");
        public static readonly InternalType ErrorType = new InternalType("<error>");

        readonly string name;

        InternalType(string name)
            : base(MemberKind.InternalCompilerType, null, null, null, Modifiers.@public) {
            this.name = name;
            this.definition2 = this;
            cache = MemberCache.Empty;

            // Make all internal types CLS-compliant, non-obsolete
            resolveFlags = (resolveFlags & ~(ResolveFlags.Obsolete_Undetected | ResolveFlags.MissingDependency_Undetected));
        }

        #region Properties

        PackageDefinition ITypeDefinition.DeclaringAssembly {
            get {
                throw new NotImplementedException();
            }
        }

        bool ITypeDefinition.IsComImport {
            get {
                return false;
            }
        }

        bool IMemberDefinition.IsImported {
            get {
                return false;
            }
        }

        bool ITypeDefinition.IsTypeForwarder {
            get {
                return false;
            }
        }

        bool ITypeDefinition.IsCyclicTypeForwarder {
            get {
                return false;
            }
        }

        string ITypeDefinition.Namespace {
            get {
                return null;
            }
        }

        int ITypeDefinition.TypeParametersCount {
            get {
                return 0;
            }
        }

        MemberReference.GenericParameter[] ITypeDefinition.TypeParameters {
            get {
                return null;
            }
        }

        #endregion

        public override string GetSignatureForError() {
            return name;
        }

        #region ITypeDefinition Members

        TypeReference ITypeDefinition.GetAttributeCoClass() {
            return null;
        }

        string ITypeDefinition.GetAttributeDefaultMember() {
            return null;
        }

        AttributeUsageAttribute ITypeDefinition.GetAttributeUsage(PredefinedAttribute pa) {
            return null;
        }

        bool ITypeDefinition.IsInternalAsPublic(PackageDefinition assembly) {
            throw new NotImplementedException();
        }

        void ITypeDefinition.LoadMembers(TypeReference declaringType, bool onlyTypes, ref MemberCache cache) {
            throw new NotImplementedException();
        }

        ObsoleteAttribute IMemberDefinition.GetAttributeObsolete() {
            return null;
        }

        void IMemberDefinition.SetIsAssigned() {
        }

        void IMemberDefinition.SetIsUsed() {
        }

        #endregion


        string IMemberDefinition.name {
            get { throw new NotImplementedException(); }
        }
    }

    //
    // Common base class for composite types
    //
    public abstract class ElementTypeSpec : TypeReference, ITypeDefinition {
        protected ElementTypeSpec(MemberKind kind, TypeReference element, MetaType info)
            : base(kind, element.containerType, null, info, element.modifiers) {
            this.Element = element;

            resolveFlags &= ~SharedStateFlags;
            resolveFlags |= (element.resolveFlags & SharedStateFlags);

            if (element.BuiltinType == BuiltinTypeSpec.Type.Dynamic)
                resolveFlags |= ResolveFlags.HasDynamicElement;

            // Has to use its own type definition instead of just element definition to
            // correctly identify itself for cases like x.MemberDefininition == predefined.MemberDefinition
            this.definition2 = this;

            cache = MemberCache.Empty;
        }

        #region Properties

        public TypeReference Element { get; private set; }

        bool ITypeDefinition.IsComImport {
            get {
                return false;
            }
        }

        bool ITypeDefinition.IsTypeForwarder {
            get {
                return false;
            }
        }

        bool ITypeDefinition.IsCyclicTypeForwarder {
            get {
                return false;
            }
        }

        #endregion

        public override ObsoleteAttribute GetAttributeObsolete() {
            return Element.GetAttributeObsolete();
        }

        protected virtual string GetPostfixSignature() {
            return null;
        }

        public override string GetSignatureForError() {
            return Element.GetSignatureForError() + GetPostfixSignature();
        }

        public override TypeReference Mutate(TypeParameterMutator mutator) {
            var me = Element.Mutate(mutator);
            if (me == Element)
                return this;

            var mutated = (ElementTypeSpec)MemberwiseClone();
            mutated.Element = me;
            mutated.metaInfo = null;
            return mutated;
        }

        #region ITypeDefinition Members

        PackageDefinition ITypeDefinition.DeclaringAssembly {
            get {
                return Element.MemberDefinition2.DeclaringAssembly;
            }
        }

        bool ITypeDefinition.IsInternalAsPublic(PackageDefinition assembly) {
            return Element.MemberDefinition2.IsInternalAsPublic(assembly);
        }

        public string Namespace {
            get { throw new NotImplementedException(); }
        }

        public int TypeParametersCount {
            get {
                return 0;
            }
        }

        public MemberReference.GenericParameter[] TypeParameters {
            get {
                throw new NotSupportedException();
            }
        }

        public TypeReference GetAttributeCoClass() {
            return Element.MemberDefinition2.GetAttributeCoClass();
        }

        public string GetAttributeDefaultMember() {
            return Element.MemberDefinition2.GetAttributeDefaultMember();
        }

        public void LoadMembers(TypeReference declaringType, bool onlyTypes, ref MemberCache cache) {
            Element.MemberDefinition2.LoadMembers(declaringType, onlyTypes, ref cache);
        }

        public bool IsImported {
            get {
                return Element.MemberDefinition2.IsImported;
            }
        }

        public void SetIsAssigned() {
            Element.MemberDefinition2.SetIsAssigned();
        }

        public void SetIsUsed() {
            Element.MemberDefinition2.SetIsUsed();
        }

        #endregion

        public new string name {
            get { throw new NotImplementedException(); }
        }
    }

    public class ArrayContainer : ElementTypeSpec {
        public struct TypeRankPair : IEquatable<TypeRankPair> {
            TypeReference ts;
            int rank;

            public TypeRankPair(TypeReference ts, int rank) {
                this.ts = ts;
                this.rank = rank;
            }

            public override int GetHashCode() {
                return ts.GetHashCode() ^ rank.GetHashCode();
            }

            #region IEquatable<Tuple<T1,T2>> Members

            public bool Equals(TypeRankPair other) {
                return other.ts == ts && other.rank == rank;
            }

            #endregion
        }

        readonly int rank;
        readonly ModuleDefinition module;

        private ArrayContainer(ModuleDefinition module, TypeReference element, int rank)
            : base(MemberKind.ArrayType, element, null) {
            this.module = module;
            this.rank = rank;
        }

        public int Rank {
            get {
                return rank;
            }
        }

        public MethodInfo GetConstructor() {
            var mb = module.Builder;

            var arg_types = new MetaType[rank];
            for (int i = 0; i < rank; i++)
                arg_types[i] = Compiler.BuiltinTypes.Int.GetMetaInfo();

            var ctor = mb.GetArrayMethod(
                GetMetaInfo(), ConstructorDefinition.ConstructorName,
                CallingConventions.HasThis,
                null, arg_types);

            return ctor;
        }

        public MethodInfo GetAddressMethod() {
            var mb = module.Builder;

            var arg_types = new MetaType[rank];
            for (int i = 0; i < rank; i++)
                arg_types[i] = Compiler.BuiltinTypes.Int.GetMetaInfo();

            var address = mb.GetArrayMethod(
                GetMetaInfo(), "Address",
                CallingConventions.HasThis | CallingConventions.Standard,
                ReferenceContainer.MakeType(Element).GetMetaInfo(), arg_types);

            return address;
        }

        public MethodInfo GetGetMethod() {
            var mb = module.Builder;

            var arg_types = new MetaType[rank];
            for (int i = 0; i < rank; i++)
                arg_types[i] = Compiler.BuiltinTypes.Int.GetMetaInfo();

            var get = mb.GetArrayMethod(
                GetMetaInfo(), "Get",
                CallingConventions.HasThis | CallingConventions.Standard,
                Element.GetMetaInfo(), arg_types);

            return get;
        }

        public MethodInfo GetSetMethod() {
            var mb = module.Builder;

            var arg_types = new MetaType[rank + 1];
            for (int i = 0; i < rank; i++)
                arg_types[i] = Compiler.BuiltinTypes.Int.GetMetaInfo();

            arg_types[rank] = Element.GetMetaInfo();

            var set = mb.GetArrayMethod(
                GetMetaInfo(), "Set",
                CallingConventions.HasThis | CallingConventions.Standard,
                Compiler.BuiltinTypes.Void.GetMetaInfo(), arg_types);

            return set;
        }

        public override MetaType GetMetaInfo() {
            if (metaInfo == null) {
                if (rank == 1)
                    metaInfo = Element.GetMetaInfo().MakeArrayType();
                else
                    metaInfo = Element.GetMetaInfo().MakeArrayType(rank);
            }

            return metaInfo;
        }

        protected override string GetPostfixSignature() {
            return GetPostfixSignature(rank);
        }

        public static string GetPostfixSignature(int rank) {
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            for (int i = 1; i < rank; i++) {
                sb.Append(",");
            }
            sb.Append("]");

            return sb.ToString();
        }

        public static ArrayContainer MakeType(ModuleDefinition module, TypeReference element) {
            return MakeType(module, element, 1);
        }

        public static ArrayContainer MakeType(ModuleDefinition module, TypeReference element, int rank) {
            ArrayContainer ac;
            var key = new TypeRankPair(element, rank);
            if (!module.ArrayTypesCache.TryGetValue(key, out ac)) {
                ac = new ArrayContainer(module, element, rank);
                ac.baseClass = Compiler.BuiltinTypes.Array;
                ac.baseInterfaces = ac.baseClass.baseInterfaces;

                module.ArrayTypesCache.Add(key, ac);
            }

            return ac;
        }

        public override List<MissingTypeSpecReference> ResolveMissingDependencies(MemberReference caller) {
            return Element.ResolveMissingDependencies(caller);
        }
    }

    class ReferenceContainer : ElementTypeSpec {
        private ReferenceContainer(TypeReference element)
            : base(MemberKind.Class, element, null)	// TODO: Kind.Class is most likely wrong
        {
        }

        public override MetaType GetMetaInfo() {
            if (metaInfo == null) {
                metaInfo = Element.GetMetaInfo().MakeByRefType();
            }

            return metaInfo;
        }

        public static ReferenceContainer MakeType(TypeReference element) {
            ReferenceContainer pc;
            if (!Compiler.currentModule.ReferenceTypesCache.TryGetValue(element, out pc)) {
                pc = new ReferenceContainer(element);
                Compiler.currentModule.ReferenceTypesCache.Add(element, pc);
            }

            return pc;
        }
    }

    class PointerContainer : ElementTypeSpec {
        private PointerContainer(TypeReference element)
            : base(MemberKind.PointerType, element, null) {
        }

        public override MetaType GetMetaInfo() {
            if (metaInfo == null) {
                metaInfo = Element.GetMetaInfo().MakePointerType();
            }

            return metaInfo;
        }

        protected override string GetPostfixSignature() {
            return "*";
        }

        public static PointerContainer MakeType(ModuleDefinition module, TypeReference element) {
            PointerContainer pc;
            if (!module.PointerTypesCache.TryGetValue(element, out pc)) {
                pc = new PointerContainer(element);
                module.PointerTypesCache.Add(element, pc);
            }

            return pc;
        }
    }

    public class MissingTypeSpecReference {
        public MissingTypeSpecReference(TypeReference type, MemberReference caller) {
            Type = type;
            Caller = caller;
        }

        public TypeReference Type { get; private set; }
        public MemberReference Caller { get; private set; }
    }
}
